package interview;

import java.util.Stack;

public class interview_03_05 {
    class SortedStack {

        private Stack<Integer> stack;
        private Stack<Integer> minstack;
        public SortedStack() {
            stack=new Stack<>();
            minstack=new Stack<>();
        }

        public void push(int val) {
            stack.push(val);
            if(minstack.isEmpty()||val<=minstack.peek()){
                minstack.push(val);
            }
        }

        public void pop() {
            if(stack.isEmpty()) return;
            int tmp=minstack.pop();
            Stack<Integer> tempstack=new Stack<>();
            while(stack.peek()!=tmp){
                tempstack.push(stack.pop());
            }
            stack.pop();
            while(!tempstack.isEmpty()){
                this.push(tempstack.pop());
            }
        }

        public int peek() {
            if(minstack.isEmpty()) return -1;
            return minstack.peek();
        }

        public boolean isEmpty() {
            return stack.isEmpty();
        }
    }
}
